//
// Created by 紫霄 on 2020/4/18.
//

#ifndef LEETCODE_28_H
#define LEETCODE_28_H
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 * 请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

    1
   / \
  2   2
 / \ / \
3  4 4  3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

    1
   / \
  2   2
   \   \
   3    3

 */
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
  bool isSymmetric(TreeNode *root) {
    if (root) {
      if ((root->left) && (root->right) &&
          (root->left->val == root->right->val)) {
        return symmetryLeftRight(root->left, root->right);
      } else {
        return (root->left == nullptr) && (root->right == nullptr);
      }
    }
    return true;
  }

  bool symmetryLeftRight(TreeNode *left, TreeNode *right) {
    if ((left->left == nullptr) && (left->right == nullptr) &&
        (right->left == nullptr) && (right->right == nullptr)) {
      return true;
    }
    if (((left->right == nullptr) && right->left) ||
        ((left->left == nullptr) && right->right)) {
      return false;
    }
    if (((right->right == nullptr) && left->left) ||
        ((right->left == nullptr) && left->right)) {
      return false;
    }

    if ((left->left == nullptr) && (right->right == nullptr)) {
      if (left->right->val == right->left->val) {
        return symmetryLeftRight(left->right, right->left);
      } else
        return false;
    }

    if ((left->right == nullptr) && (right->left == nullptr)) {
      if (left->left->val == right->right->val) {
        return symmetryLeftRight(left->left, right->right);
      } else
        return false;
    }
    if ((left->left->val == right->right->val) &&
        (left->right->val == right->left->val)) {
      return (symmetryLeftRight(left->left, right->right) &&
              symmetryLeftRight(left->right, right->left));
    }
    return false;
  }
};
#endif // LEETCODE_28_H
